package programming.in.scala

/**
  * Created by shichen on 2017/6/5.
  *
  * List are quite similar to arrays, but there are two important differences.
  * First,lists are immutable and cannot changed by assignment,
  * Second, lists have a recursive structure(ie., a linked list), whereas arrays are flat
  */
object ch16List extends App{
  val fruit = List("apples","orange","pears")
  val fruit2 = "apples" :: ("orange" :: ("pears" :: Nil))
  val num = List(1,2,4,3)
  num.diff(List(1)) //相当于删除特定item

  val num2 = 1 :: 2 :: 3 :: 4 :: Nil //Nil represents the empty list
  //: operator associates to the right
  println(fruit2,num2)
  val diag3 = // diag3 is List[List[Int]]
    List(List(1,0,0),
    List(0,1,0),
    List(0,0,1)
  )
  val empty = List()
  val empty2: List[Nothing] = List()
  //empty.head; empty2.tail //head,tail only aims to non-empty list, or except occurr

  val xs: List[String] = List() //Nothing is subtype of any type in scala
  //and List type is covariant, so List[Nothing] can also be seen as an object
  //of every other list type of form List[T]

  //////////////////////////////////////pattern match
  val List(a,b,c) = fruit
  println("List pattern match:" + a)
  val d :: e :: rest = num //如果不清楚数目，就用::
  println("List pattern match:" + d,e)

  println("insert sort:" + isort(num))

  //highOrderFunc()

  //用模式匹配的方式写插入排序
  def isort2(xs: List[Int]): List[Int] = xs match {
    case List() => List()
    case x :: xs => insert(x,isort2(xs))
  }
  def insert2(x: Int, xs: List[Int]): List[Int] = xs match {
    case List() => List(x)
    case y :: ys => if (x <= y) x :: xs else y :: insert(x,ys)
  }

  //自行实现::: 操作
  def append[T](xs: List[T], ys: List[T]): List[T] = {
    xs match {
      case List() => ys
      case x :: xs1 => x :: append(xs1,ys)
    }
  }

  //用:::实现reverse(这不高效)
  def rev[T](xs: List[T]): List[T] = xs match {
    case List() => xs
    case x :: xs1 => rev(xs1) ::: List(x)
  }

  def firstOrderMethod() {
    num.take(2);//取前面的2个
    num.drop(2);//丢弃前面的2个
    num.splitAt(2)
    println(num.apply(0)) //索引操作相当于调用apply,但复杂度是O(n)

    println("flatten:" + diag3.flatten) //flatten it out a single list
    println(fruit.map(_.toCharArray).flatten)
    //num.flatten //element是List时才可以用flatten

    val listPair = num.zip(fruit)
    println("zip:" + listPair + "  " + `type`(listPair).toString()) //把两个List编成对，大小不一致时丢掉未匹配的
    println(fruit.zipWithIndex) //将值与索引编成对

    println("mkString:" + fruit.mkString("[", ",", "]"))
    println(fruit.mkString) //相当于mkString("")

    val buf = new StringBuilder
    fruit.addString(buf, "(", ",", ")")
    println("strinbbuilder:" + buf)

    num.toArray.toList

    //iterator
    val it = num.iterator
    println("iterator:" + it.next())
  }

  def highOrderFunc(): Unit = {
    println("\nhigh order method...")
    val fruit = List("apples","orange","pears")
    val num = List(1,2,4,3)
    println(num.map(_ + 1))
    println(fruit.map(_.length))

    println(fruit.map(_.toList)) //返回List[List[]]
    println(fruit.flatMap(_.toList)) //flatMap returns a single list in which all element
    //lists are concatenated

    println(List.range(1,5).flatMap(
      i => List.range(1,i).map(j => (i,j)))
    )
    //上面的元组List也可这样生成：
    for (i <- List.range(1,5); j <- List.range(1,i)) yield (i,j)


    var sum = 0
    List.range(1,6).foreach(sum += _) //foreach所接是一个返回Unit类型的过程，与map不一样


    println("filter:" + List.range(1,10).filter(_ % 2 == 0))
    fruit.filter(_.length == 5)

    println("partition:" + List.range(1,10).partition(_ % 2 == 0)) //返回a pair of List(一个满足条件，另一个不)

    println("find:" + List.range(1,3).find(_ == 4)) //返回Option对象
    println("takeWhile:" + List(1,2,3,-4,5).takeWhile(_ > 0)) //返回满足条件最长的List
    println("dropWhile:" + List(1,2,3,-4,-6,5).dropWhile(_ > 0))
    println("span:" + List(1,2,3,-4,-6,5).span(_ > 0)) //返回满足条件的和不满足条件的List

    println("forall:" + List.range(1,9).forall(_ > 0)) //都满足条件就返回true
    println("exists:" + List(1,-1).exists(_ < 0)) //有一个满足条件就返回true

    println(("" /: fruit)(_ + " " + _))
    def sum2(xs: List[Int]): Int = (0 /: xs)(_ + _) //相当于0+List(0) + List(1)+..., 0是初使值
    println((fruit.head /: fruit.tail)(_ + ":" + _))

    //https://www.iteblog.com/archives/1228.html
    //fold/foldLeft/foldRight
    num.fold(0) { (z,i) =>
      z + i
    } //0是初使值,z是上一次的累积值，i表示下一个item
  }

  def isort(xs: List[Int]):List[Int] = {
    if (xs.isEmpty) Nil
    else insert(xs.head,isort(xs.tail))
  }
  def insert(x: Int, xs: List[Int]): List[Int] = {
    if (xs.isEmpty || x <= xs.head) x :: xs
    else xs.head :: insert(x,xs.tail)
  }

  //可以查看变量类型。用``可使得成为scala identifier.type is reserved word
  def `type`[T: Manifest](t: T): Manifest[T] = manifest[T]
}
